package com.code.leetcode._202507;

import java.util.ArrayList;
import java.util.List;

//54 螺旋矩阵
public class SpiralOrder {
    /**
     * 给你一个m行n列的矩阵matrix，请按照顺时针螺旋顺序，返回矩阵中的所有元素
     * 示例1：输入：matrix=[[1,2,3],[4,5,6],[7,8,9]]
     * 输出：[1,2,3,6,9,8,7,4,5]
     * 示例2：输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
     * 输出：[1,2,3,4,8,12,11,10,9,5,6,7]
     **/
    public static void main(String[] args) {
        SpiralOrder s = new SpiralOrder();
        System.out.println(s.spiralOrder1(new int[][]{{1,2,3,4}, {5,6,7,8}, {9,10,11,12}}));
    }

    /**
     * 模拟
     * 可以模拟螺旋矩阵的路径。初始位置是矩阵的左上角，初始方向是向右，当路径超出界限或者进入访问过的位置时，
     * 顺时针旋转，进入下一个方向。
     * 判断路径是否进入之前访问过的位置需要使用一个与输入矩阵大小相同的辅助矩阵visited，其中的每个元素表示
     * 该位置是否被访问过。当一个元素被访问时，将visited中的对应位置的元素设为已访问。
     * 如何判断路径是否结束？由于矩阵中的每个元素都被访问一次，因此路径的长度即为矩阵中的元素数量，当路径的长度
     * 达到矩阵中的元素数量时即为完整路径，将该路径返回。
     **/
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> order = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return order;
        }
        int rows = matrix.length, columns = matrix[0].length;
        boolean[][] visited = new boolean[rows][columns];
        int total = rows * columns;
        int row = 0, column = 0;
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int directionIndex = 0;
        for (int i = 0; i < total; i++) {
            order.add(matrix[row][column]);
            visited[row][column] = true;
            int nextRow = row + directions[directionIndex][0],
                    nextColumn = column + directions[directionIndex][1];
            if (nextRow < 0 || nextRow >= rows || nextColumn < 0
                    || nextColumn >= columns || visited[nextRow][nextColumn]) {
                directionIndex = (directionIndex + 1) % 4;
            }
            row += directions[directionIndex][0];
            column += directions[directionIndex][1];
        }
        return order;
    }

    /**
     * 按层模拟
     * 可以将矩阵看成若干层，首先输出最外层的元素，其次输出次外层的元素，直到输出最内层的元素
     * 定义矩阵的第k层时到最近边界距离为k的所有顶点。
     * 对于每层，从左上方开始以顺时针的顺序遍历所有元素，假设当前层的左上角位于(top,left)，右下角位于(bottom,right)
     * 按照如下顺序遍历当前层的元素。
     * 1、从左到右遍历上侧元素，依次为(top,left)到(top,right)
     * 2、从上到下遍历右侧元素，依次为(top+1,right)到(bottom,right)
     * 3、如果left<right且top<bottom，则从右到左遍历下侧元素，依次为(bottom,right-1)到(bottom,left+1)
     * 以及从下到上遍历左侧元素，依次为(bottom,left)到(top+1,left)
     * 遍历完当前层的元素之后，将left和top分别增加1，将right和bottom分别减少1，进入下一层继续遍历，直到遍历完所有元素为止。
     **/
    public List<Integer> spiralOrder1(int[][] matrix) {
        List<Integer> order = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return order;
        }
        int rows = matrix.length, columns = matrix[0].length;
        int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
        while (left <= right && top <= bottom) {
            for (int column = left; column <= right; column++) {
                order.add(matrix[top][column]);
            }
            for (int row = top + 1; row <= bottom; row++) {
                order.add(matrix[row][right]);
            }
            if (left < right && top < bottom) {
                for (int column = right - 1; column > left; column--) {
                    order.add(matrix[bottom][column]);
                }
                for (int row = bottom; row > top; row--) {
                    order.add(matrix[row][left]);
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        return order;
    }
}

